\documentclass[letterpaper,onecolumn,10pt]{article}
\usepackage{graphicx}
\usepackage{algorithmicx}
\usepackage{algpseudocode}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage[usenames,dvipsnames]{color}
\usepackage{hyperref}
\usepackage{tikz}
\usepackage{pgfplots}
\usetikzlibrary{calc,matrix,shapes,decorations,backgrounds,fit,shapes.geometric}
\usepackage{array}
\usepackage{parskip}
\newcolumntype{L}[1]{>{\raggedright\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
\newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
\newcolumntype{R}[1]{>{\raggedleft\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}

% Define root path
%\def \ROOTPATH {/Users/harper/Repositories/research-papers-hao/template/}
\def \ROOTPATH {/home/harper/Repositories/research-papers-hao/template/}


\graphicspath{\ROOTPATH{image/}}

\begin{document}
\date{}

\title{\Large \bf A Internet Topology query platform based on CAIDA data}

% For pdflatex
\setlength{\pdfpagewidth}{8.5in}
\setlength{\pdfpageheight}{11in}

% Copy setting from USENIX
\setlength{\textheight}{9.0in}
\setlength{\columnsep}{0.25in}
\setlength{\textwidth}{6.50in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}

\setlength\parindent{0pt}
\setlength\parskip{4px}

%for single author (just remove % characters)
\author{
{\rm Hao Jiang \qquad Jeanna N. Matthews}\\
Clarkson University
% copy the following lines to add more authors
% \and
% {\rm Name}\\
%Name Institution
} % end author

\maketitle


%--------------------------------------------------------------------
\section*{Background, Motivation and Purpose}

In all distributed system, it is vital to know in advance the network connectivity between two possible locations. Useful information includes network path length, latency estimation, possible traffic congestion.  These information can be provided by a Internet Topology. A Internet Topology is a basically a network map that provides network paths between two IPs. Additional info including latency, geographic mapping can also be provided. 

Technologies to build a Internet Topology generally involve traceroute and alias resolution. Traceroute is used to collect network paths and inter-node latencies. Alias resolving will group different IPs that belong to the same router together so that no false new network path is introduced. There're also some routers that don't respond to an expired packet, thus they will be listed as missing in traceroute results. Till now I see no research addressing this part. 

The platform I want to build is based on CAIDA's data including traceroute and alias resolving result. A static topology is provided every half year. Based on this static topology, we can build a topology then add traffic information represented by traceroute data to it.
%--------------------------------------------------------------------
\section*{Previous work and Why we need a new one}

\cite{madhyastha_2006} propose iPlane platform in 2006. They use PlanetLab nodes to issue traceroute data to over 147k prefixes and generate Internet Topology from them. They then use latency from the traceroute data to estimate end-to-end latencies.

CAIDA \cite{keys_2010} provide similar data in a much wider range. CAIDA conducts daily traceroute information from 199 monitors to ALL prefix \textbackslash 24, which provide live data of network performance. They generate routers and links from these data using various techniques, making the topology data readily available.

In \cite{huffaker_2012}, Huffaker et al. publishes a technical report doing comparison between platforms that provides Internet Topology. They claims that CAIDA has the most complete data and iPlane the least. As CAIDA keeps providing scheduled updated data, we think it is better to use CAIDA's data for our purpose.

The purpose of our platform is not only topology and latency. Besides these information that can be retrieved directly from CAIDA dataset, we would like to use traceroute to find most busy paths. Network links that is shared by more traceroute paths are assumed to be more busy, and thus have a higher chance to have congestion. We also want to see the possibility to use topology data to find missing hops in traceroute result. 

We also implement a new distributed system for this purpose. There are already many general-purpose distributed graph system exist. Examples: Pregel\cite{malewicz_2010}, PowerGraph\cite{joseph_2012} and GraphX\cite{gonzalez_2014}. Reason that we don't use them directly: Pregel is based on a vertex model which update each vertex each round and send message to other vertices. This doesn't fit our purpose in which the general operation is path finding. (Is this true? Path finding can also be done using messages. )

All previous system can be viewed as batch processing system, that is, doing calculation on a huge graph and output result. Pregel PowerGraph and GraphX all assume that all data in a partition (or other correpsondence) need to be processed. However, in our problem only some data need to be processed instead of all.

%--------------------------------------------------------------------

\section*{System Design}


\begin{figure}
\centering
\begin{tikzpicture}
[
	every node/.style={text centered},
	layer/.style={rectangle, draw=gray!90, fill=red!10, line width={1pt}, minimum width={7cm}, minimum height={1.5cm}}
]
\matrix[matrix of nodes, row sep= {0mm}, column sep={1mm}] {
	\node[layer, fill=blue!10, anchor= east](ut) {Universal Traceroute};\\
	\node[layer, fill=yellow!20, anchor= east, text width={8cm}](ta) {Traceroute Analysis};\\
	\node[layer, fill=green!20, text width={10cm}, anchor= east](it) {Internet Topology};\\
};

%\draw[layer] (it.west |- ut.north) coordinate (aux1) rectangle ($(ta.south west) - (0mm,0mm)$) coordinate (aux2) {};

\draw[layer] (it.west |- ut.north) coordinate (aux1) -- (it.west |- it.north) -- (ta.south west) coordinate (aux2) -- (ta.north west)  -- (ut.west |- ta.north) -- (ut.north west) -- (it.west |- ut.north){};
\node[text width = 2cm,xshift = {1.5cm}, yshift={-1cm}](X) at (aux1) {Programming API};


\end{tikzpicture}
\caption{System Structure}
\end{figure}


Our system consists of the following parts:
\begin{itemize}
\item \textbf{Internet Topology} Construct a internet topology consisting of routers, ips and links. This can be used to view possible connections between network nodes. This module is based on CAIDA's ITDK dataset \cite{caida_itdk}.
\item \textbf{Traceroute Analysis} We get inter-node latency information from traceroute paths and apply them to the topology in realtime. Also, a path that has been used by multiple traceroute records should also have heavily traffic in realworld. We can find possible congestion paths. This data is updated every day, thus we need to provide a high performance processing  
\item \textbf{Programming API} We provide realtime query for Internet Topology and Traceroute data. This includes traffic and latency between nodes. It also provides API for user the functionality to run vertex programs.
\item \textbf{Universal Traceroute} Previous tools including traceroute, reverse-traceroute all require users to have control to the source machine. It is not possible for them to do traceroute between two IP addresses that are not under management. Routing is destination based. With enough traceroute data, we can do an universal traceroute that predict network path between two arbitrary IP addresses.
\end{itemize}

\subsection*{Build an Internet Topology}

Internet Topology provides a connectivity map between IP addresses. It also works as a backbone of the entire system.  We design it to be  working on a distributed system. The data is split into partitions. Each partition consists of several datasets, which are stored in disk and loaded to memory when necessary. As is in \cite{joseph_2012}, the partition is split on vertex.

Node dataset includes routers' IP addresses, links, AS number and geolocation. Unlike other big graph that use hash to randomly distribute nodes to different partitions, router nodes can be naturally partitioned by country boundary.  

Link dataset contains node connectivity info. Each link is a shared bus connecting multiple routers. These routers can reach each other with a single hop in a network path. For some routers the IP address information is also included. Link data is originally in the format of 
\[
link <link\_id>: (<node\_id>(:<ip>)?[\ ])+<node\_id>(:<ip>)?
\]
Our primary operation regarding links is to look for nodes that connect to a specific node. This operation can be separated into two steps 1) look for links that connect to the current node 2) look for nodes connecting to a given link. The second operation can be done directly by indexing on the link datafile, while the first one require an look for links based on node. This requires a datafile in the following format:
\[
<node\_id>(:<ip>)?: (<link\_id>[\ ])+<link\_id>
\] 

Index facilitate fast search for node and link information. It is used for effectively loading data from file to memory. There are around 56 million nodes and the index will occupy around 2.5G memory. In this case we need a file based index. Considering the implementation effort, we will first use java's object serialization to implement the file index. This can be changed later if it has been proven that file size is a bottleneck. Index is now built as a shared sturcutre between different nodes and will be put on a distributed system like HDFS. It can be split into small pieces and used only by one node with no further effort.

Routing provides information that which partition are sharing vertex with current partition. An operation that involves a vertex on cut will be propagate to other partitions. 

%We also support a "node movement" operation to decrease inter-machine communication.

\begin{figure}
\centering
\begin{tikzpicture}
[
	every node/.style={text centered},
	layer/.style={rectangle, draw=gray!90, fill=yellow!10, line width={1pt}, minimum width={5cm}, minimum height={1cm}}
]
\matrix[matrix of nodes, row sep={2mm}, column sep={8mm}] {
\node(title1) {Partition 1}; & \node(title2) {Partition 2}; \\
\node[layer](node1){Node}; & \node[layer](node2){Node}; \\
\node[layer](edge2){Edge};  & \node[layer](edge2){Edge}; \\
\node[layer](routing1){Routing}; & \node[layer](routing2){Routing};\\
};

\node[layer, yshift= -1.5cm, xshift = 0.5cm, minimum width={11cm},minimum height={1.5cm}]at (routing1.south east)(index){Index}; 

\begin{scope}[on background layer]
\node[rounded corners, fit={($(node1.north west)+(-2mm,8mm)$)($(routing1.south east)+(2mm,-2mm)$)}, fill=blue!10]{};
\node[rounded corners, fit={($(node2.north west)+(-2mm,8mm)$)($(routing2.south east)+(2mm,-2mm)$)}, fill=blue!10]{};
\end{scope}
\end{tikzpicture}
\caption{Internet Topology on single machine}
\end{figure}

\subsection*{Traceroute Analysis}


\subsection*{Universal Traceroute}

\bibliographystyle{plain}
\bibliography{reference}
\end{document}